#pragma once
#include <iostream>
#include <cassert>
#include <cstring>
#include <thread>
#include <mutex>
#include <unordered_map>

#ifdef _WIN32
#include <windows.h>
const size_t PAGE_SHIFT = 13; // 一页8k，2^13字节
#else
#include <sys/mman.h>
const size_t PAGE_SHIFT = 12; // 一页4k，2^12字节
#endif

using std::cout;
using std::endl;

// extern size_t pageCount; // debug
const size_t MAX_BYTES = 256 * 1024; // ThreadCache能分配的最大字节数
const size_t NFREELISTS = 208;       // 自由链表哈希桶的数量
const size_t NPAGES = 129;           // PageCache的最大桶号，同时也是页内存的最大页数

#ifdef _WIN64
typedef unsigned long long pageid_t;
const size_t BIT_WIDTH = 64;
#elif _WIN32
typedef size_t pageid_t;
const size_t BIT_WIDTH = 32;
#elif __x86_64__ // Linux 64位下
const size_t BIT_WIDTH = 64;
typedef unsigned long long pageid_t;
#else            // Linux 32位下
const size_t BIT_WIDTH = 32;
typedef size_t pageid_t;
#endif

// 直接向系统按页申请空间
inline static void *SystemAlloc(size_t kpage)
{
#ifdef _WIN32
    void *memory = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // linux下
    void *memory = mmap(NULL, kpage << PAGE_SHIFT, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (memory == MAP_FAILED)
    {
        perror("SystemAlloc");
        exit(errno);
    }
    // pageCount += kpage; // debug
    // cout << std::this_thread::get_id() << ": SystemAlloc " << kpage << "pages" << endl; // debug
    return memory;

#endif
    if (memory == nullptr)
        throw std::bad_alloc();
    return memory;
}

// 将空间直接释放给系统
inline static void SystemDealloc(void *mem, size_t kpage)
{
#ifdef _WIN32
    VirtualFree(mem, 0, MEM_RELEASE);
#else
    int ret = munmap(mem, kpage << PAGE_SHIFT);
    if (ret == -1)
    {
        perror("SystemDealloc");
        exit(errno);
    }
    // pageCount -= kpage; // debug
    // cout << std::this_thread::get_id() << ": SystemDealloc " << kpage << "pages" << endl; // debug
#endif
}

// 取obj内存块的头4/8字节强转成指针返回其引用（在外面可读可写）
static void *&NextObj(void *obj)
{
    // 将obj解释为指向void*类型的指针，并解引用（取其指向内存的引用）
    return *(void **)obj;

    // 下面对比几种错误写法
    // return (int)obj | *(int*)obj;
    // 要操控的是obj指向的内存块，而不是obj的值，因此要强转成指针类型

    // return *(void*)obj | *(void**)obj;
    // void是空类型，其指针不能解引用，但是void*是指针类型，其二级指针可以解引用

    // return *(int*)obj | *(void**)obj;
    // 要兼容32位下的4字节指针和64位下的8字节指针

    // return *(int**)obj | *(void**)obj;
    // 从内存使用的角度没有问题，但在语法上void*可以接收任意类型的地址
}

// FreeList是ThreadCache每个桶的结构
// 就是一个简单的单链表，只有头插头删等简单操作
class FreeList
{
public:
    void Push(void *obj)
    {
        assert(obj != nullptr);
        NextObj(obj) = _freeList;
        _freeList = obj;
        ++_size;
    }

    void PushRange(void *start, void *end, size_t n)
    {
        assert(start != nullptr && end != nullptr);
        NextObj(end) = _freeList;
        _freeList = start;
        _size += n;
    }

    void *Pop()
    {
        assert(_freeList != nullptr);
        void *obj = _freeList;
        _freeList = NextObj(obj);
        --_size;
        return obj;
    }

    void PopRange(void *&start, void *&end, size_t n)
    {
        assert(n <= _size);
        start = _freeList;
        void *cur = _freeList;
        for (int i = 0; i < n; ++i)
        {
            end = cur;
            cur = NextObj(cur);
        }
        NextObj(end) = nullptr;
        _freeList = cur;
        _size -= n;
    }

    bool Empty()
    {
        return _freeList == nullptr;
    }

    size_t GetMaxSize()
    {
        return _maxSize;
    }

    void AddMaxSize()
    {
        ++_maxSize;
    }

    size_t Size()
    {
        return _size;
    }

private:
    void *_freeList = nullptr; // 自由链表的头指针
    size_t _maxSize = 1;       // 随申请次数不断递增，用于慢开始申请和内存释放
    size_t _size = 0;          // 记录链表中内存块的数量
};

// 根据内存对齐规则定制的相关算法
class AlineRule
{
    // 整体控制在最多10%左右的内碎⽚浪费
    // [1,128]                8byte对⻬        freelist[0,16) 16个
    // [128+1,1024]           16byte对⻬       freelist[16,72) 56个
    // [1024+1,8*1024]         128byte对⻬      freelist[72,128) 56个
    // [8*1024+1,64*1024]      1024byte对⻬     freelist[128,184) 56个
    // [64*1024+1,256*1024]   8*1024byte对⻬   freelist[184,208) 24个
public:
    // 返回对齐后的内存大小
    static size_t RoundUp(size_t size)
    {
        if (size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if (size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if (size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if (size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if (size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else
        {
            return _RoundUp(size, 1 << PAGE_SHIFT); // 超过MAX_BYTES，就按1页对齐
        }
    }

    // 返回指定大小的内存在ThreadCache和CentralCache中的存储桶号
    static size_t GetIndex(size_t size)
    {
        assert(size > 0 && size <= MAX_BYTES);

        if (size <= 128)
        {
            return _GetIndex(size, 3);
        }
        else if (size <= 1024)
        {
            return _GetIndex(size - 128, 4) + 16;
        }
        else if (size <= 8 * 1024)
        {
            return _GetIndex(size - 1024, 7) + 72;
        }
        else if (size <= 64 * 1024)
        {
            return _GetIndex(size - 8 * 1024, 10) + 128;
        }
        else if (size <= 256 * 1024)
        {
            return _GetIndex(size - 64 * 1024, 13) + 184;
        }
        else
        {
            assert(false);
            return -1;
        }
    }

    //返回对应桶号下内存块的大小（对齐），与GetIndex互为逆运算
    static size_t IndexToSize(size_t index)
    {
        assert(index >= 0 && index < NFREELISTS);
        if (index < 16)
        {
            return (index + 1) * 8;
        }
        else if (index < 72)
        {
            return 128 + (index - 15) * 16;
        }
        else if (index < 128)
        {
            return 1024 + (index - 71) * 128;
        }
        else if (index < 184)
        {
            return 8 * 1024 + (index - 127) * 1024;
        }
        else
        {
            return 64 * 1024 + (index - 183) * 8 * 1024;
        }
    }

    // 返回对应大小内存块的批数量上限
    static size_t BatchNumMax(size_t alineSize)
    {
        assert(alineSize > 0 && alineSize <= MAX_BYTES);
        // size越小，批数量上限越大，反之则越小
        size_t batchNum = MAX_BYTES / alineSize;
        // 设定一个批数量的上下界[2,512]，防止分配过多
        if (batchNum < 2)
            batchNum = 2;
        else if (batchNum > 512)
            batchNum = 512;
        return batchNum;
    }

    // 根据内存块的大小计算向PageCache申请的页内存的大小（单位：页）
    static size_t SizeMovePage(size_t alineSize)
    {
        size_t batchNum = BatchNumMax(alineSize);
        size_t npage = batchNum * alineSize;
        npage >>= PAGE_SHIFT;
        if (npage == 0)
            npage = 1;
        return npage;
    }

    // 位运算：
    static size_t _RoundUp(size_t size, size_t alineNum)
    {
        return size + (alineNum - 1) & ~(alineNum - 1);
    }

private:
    // 一般写法：
    // static size_t _RoundUp(size_t size, size_t alineNum)
    // {
    //     if (size % alineNum != 0)
    //         return (size / alineNum + 1) * alineNum;
    //     else
    //         return (size / alineNum * alineNum);
    // }

    // 一般写法：
    // static size_t _GetIndex(size_t size, size_t alineNum)
    // {
    //     if (size % alineNum == 0)
    //         return size / alineNum - 1;
    //     else
    //         return size / alineNum;
    // }

    // 位运算：
    static size_t _GetIndex(size_t size, size_t aline_shift)
    {
        return (size + ((1 << aline_shift) - 1) >> aline_shift) - 1;
    }
};

// Span是CentralCache和PageCache的内存管理单元
struct Span
{
    pageid_t _pageId = 0; // 大块内存起始页的页号
    size_t _pageNum = 0;  // 页的数量

    Span *_next = nullptr; // 双链表的链接结构
    Span *_prev = nullptr;

    size_t _useCount = 0;      // 分配出去的小块内存计数
    size_t _objSize = 0;       // 小块内存的大小
    bool _isUse = false;       // 是否已经分配给CentralCache使用
    void *_freeList = nullptr; // 挂接切好的小块内存（单链表）
};

// SpanList是CentralCache和PageCache每个桶的结构
// 考虑到SpanList有任意位置插入删除的需求，所以采用带头双向循环链表结构
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }

    ~SpanList()
    {
        delete _head;
    }

    void Insert(Span *pos, Span *newSpan)
    {
        assert(pos != nullptr);
        assert(newSpan != nullptr);

        Span *prev = pos->_prev;
        prev->_next = newSpan;
        newSpan->_prev = prev;
        newSpan->_next = pos;
        pos->_prev = newSpan;
    }

    void Erase(Span *pos)
    {
        assert(pos != nullptr);
        assert(pos != _head);

        Span *prev = pos->_prev;
        Span *next = pos->_next;
        prev->_next = next;
        next->_prev = prev;
        // 之后不能释放pos位置的span，应该交由page-cache回收
    }

    void PushFront(Span *newSpan)
    {
        Insert(Begin(), newSpan);
    }

    Span *PopFront()
    {
        Span *front = Begin();
        Erase(front); // 注意！这里并没有释放其空间，只是断开了链接关系
        return front;
    }

    void Lock()
    {
        _mtx.lock();
    }

    void Unlock()
    {
        _mtx.unlock();
    }

    Span *Begin()
    {
        return _head->_next;
    }

    Span *End()
    {
        return _head;
    }

    bool Empty()
    {
        return _head->_next == _head;
    }

private:
    Span *_head;
    std::mutex _mtx;
};